﻿#define _CRT_SRCURE_NO_WARNINGS 1
#pragma  warning (disable:4996)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


void PrintArray(int* arr, int n);
void InsertSort(int* arr, int n);
//时间复杂度：
//最坏情况：等差数列  --  O(N²) 第一次最坏排1次，第二次最坏排两次，第三次最坏排三次，第四次最坏排四次，一直往上加就是个等差数列
//最好情况：有序数列  --  O(N) 

void ShellSort(int* arr, int n);
//分成gap组，每组N/gap个数据。
//每组最坏的情况下的挪动次数：1 + 2 + 3 + …… + N / gap - 1 等差数列
//总次数：(1 + 2 + 3 + …… + N / gap - 1) * gap次。这个次数没算外层的while循环
//int gap = n;
//while (gap > 1)
//{
//	gap = gap / 3 + 1;
//}

//最开始gap很大：(N / 3 + 1)，代入到总次数可得(1 + 2 + …… 3)* (N / 3 + 1)，很接近于O(N)
//……
//快结束时，gap很小，带入到总次数可得总次数接近于等差数列，应该是O(N²)，但其实并不是，因为这是最后的一次预排序，接近有序，所以是O(N)
//
//我们可以将每一次的预排序的运行次数看作O(N)
//
//N/3/3/3/3……/3/3/3=1
//N/2/2/2/2……/2/2/2=1
//所以预排序的次数是logN，2和3作为log的底数我们不管。所以次数就是logN
//
//那我们毛估出来的希尔排序的时间复杂度和堆排序其实是平分秋色，不相上下。
//但希尔排序的这个时间复杂度并不就是这个N*logN，因为我们是毛估出来的，就是想突出希尔排序相对于直接插入排序的效率要高很多。
//
//各个预排序的所耗时间加起来其实都是远小于我们直接排序的。
//
//中间的预排序的时间复杂度不一定是O(N)，因为中间的gap开始变小一些了，总次数左右两边都开始趋于N，也就不能忽略了，有点类似于N²了。
//预排序的时间复杂度像一个热气球模型一样，时间消耗先上去后又下来。


//结论：希尔排序时间复杂度：O(N的1.3次方)

//其实主要计算的难点就在于，中间的预排序的时间复杂度随着预排序的次数的增加在不断地变化，这就导致计算次数上是比较难的。

//对于gap的选择，除3加1还是比较好的。

void SelectSort(int* arr, int n);

void HeapSort(int* arr, int n);
//堆排序同样作为选择排序，可惜比选择排序不知道强了多少倍，归根结底是因为堆排序选数的方式不一样。
//升序建大堆，降序建小堆
//最坏情况就是每次都要调整高度次，高度又是logN，选N次数据摆到堆顶，所以时间复杂度就是N*logN。

void BubbleSort(int* arr, int n);
//时间复杂度：O(N²)  最坏情况下的话，第一次交换次数为N-1，第二次N-2，最后一次交换0次，所以总次数还是个等差数列，

//插入排序，选择排序，冒泡排序比较的话，他们的时间复杂度都是O(N²)。
//如果不做优化的话，选择和冒泡其实区别不大，都需要不断地遍历数组，只不过遍历数组的次数逐渐减少。而插入情况较好的话复杂度可是O(N)
//他俩无论情况好坏时间复杂度都是O(N²)，但选择排序还比冒泡强一些，因为人家遍历一遍数组能确定两个值，你冒泡排序就确定一个值。
//所以在时间复杂度O(N²)这个量级里面，直接插入排序的适应性还是很强的，无论是整体有序，还是部分有序，适应性都很强。


void QuickSort(int* arr, int begin, int end);
//因为hoare版本需要我们递归，所以函数在参数设计上，应该设计成递归型函数的参数
//因为每次快排的数组段逐渐减小，为了方便我们的控制，我们设计两个参数，分别代表数组的首元素和尾元素下标


//快排的时间复杂度：
//1.理想状况下，每次选出的key正好在数组的正中间的话，那每一层的递归都是接近于N次的，共有logN层，那么可知时间复杂度为N*logN
//2.最坏情况下，每次选key都是最大或最小，也就是有序或逆序的情况，如果这样的话，每次的递归都要走N次，与上面不同的是，向下递归的时候
//  是无法做到拆分的，因为一次只能拆出来一个数，那其实也说明现在的快排和冒泡没什么区别，一次只能选出来一个数。

//快排的空间复杂度：
//1.快排需要递归，递归就需要建立栈帧，建立logN层栈帧，每一层的额外空间是O(1)，所以空间复杂度是O(logN)
//2.
// 
 
//有序的情况下，出现了栈溢出的问题，由此可见开辟的函数栈帧个数过多，导致了栈溢出，也就是说明递归的深度太深了，消耗的栈空间太多了，
//导致无法继续开辟栈空间，因为每次只能处理一个数，其实也就是一个二叉树，一根叉是只有一个节点，另一个叉是很深很深的子树，在同样开辟
//栈帧空间的大小下的话，你每次处理的数据却不见得很优，自然是要出问题的，如果非有序的情况下的话，我们处理的数的个数是按照指数函数递增的
//你现在处理的个数是按照n来递增的，怎么可能有2的N次方快啊
//
//计算快排的时间复杂度其实也很简单，我们只要确定递归的深度就可以了，因为每层递归的次数都是接近于N次的，所以只要看看递归的深度有多深，
//然后将两者×起来，就可得时间复杂度了

//如果使用release版本的话，每次开辟的栈帧空间其实是会小很多的，所以栈溢出的问题就不会那么容易出现了，
//因为每个栈帧空间里面都没有打调试信息,

void QuickSortNonR(int* arr, int begin, int end);
void MergeSort(int* arr, int n);
void _MergeSort(int* arr, int begin, int end, int* tmp);
//归并排序的时间复杂度：因为每一层的递归，在返回之后都要进行遍历数组元素然后归并，我说的是每一层的递归，所以每一层下来的递归，都会
// 遍历数组一遍，那么整体的时间复杂度就是O(N*logN)
//归并排序的空间复杂度：由于额外开辟了一个tmp数组，用于存放n个数组元素，所以空间复杂度就是O(N)


//快速排序：
//1.时间复杂度：O(N*logN)，有了三数取中之后，快排不会是O(N²)。
//2.空间复杂度：O(logN)
//归并排序：
//1.时间复杂度：O(N*logN)，
//2.空间复杂度：O(N+logN)，在N面前，logN可以忽略不计，所以空间复杂度就是O(N)
//
//空间复杂度算的就是算它最多需要消耗多少额外的空间，并且我们知道空间是可以重复利用的，不累计的。所以一趟最深的归并递归下来之后，就
//已经开辟好了logN个栈帧空间了，等他返回栈帧空间就销毁了，其他递归再开辟栈帧空间的时候，重复利用的是之前已经被销毁的栈帧所用的空间
//，那其实也能够说明，我们递归的空间复杂度指的就是开辟的栈帧空间的最大个数，因为递归是一个很神奇的东西，他不是你看到有多少空间，他
//就消耗了多少空间，而是，它事先开辟到最深的递归，此时开辟了多少空间，那这个算法的空间复杂度就是多少，因为后面继续递归的时候，用的是
//它之前开辟好的递归空间，在之前开辟好的空间之上重新建立函数栈帧。每次栈帧空间里面定义的变量所用空间都可以认为是O(1)

//一般递归每次建立的栈帧空间复杂度是O(1)，所以递归的空间复杂度只需要看递归的深度即可，最深会走到多少，那就是空间复杂度，因为空间是可
//以重复利用，不累计的。栈帧销毁又不是栈虚拟空间销毁，我们下次继续利用上次销毁栈帧所在空间位置开辟新的栈帧，你得分清楚西瓜和哈密瓜啊！

void MergeSortNonR(int* arr, int n);



//稳定性：对于相同的数，保证他们的相对顺序不变，那么就是稳定的，如果变了，那就是不稳定的

void CountSort(int* arr, int n);
//计数排序：额外开辟一个数组tmp，从0到arr中所给元素的最大值，遍历arr数组，某个元素出现几次，tmp中对应的下标位置的元素就+1，当然tmp
//数组都是初始化为0的。再将tmp数组中每个下标对应的值，也就是下标数字在arr中出现的次数直接写回原数组arr中，即可完成排序
//
//适合范围相对集中的数据进行计数排序处理。绝对映射和相对映射


